/**
 * The number, 1406357289, is a 0 to 9 pandigital number because it is made 
 * up of each of the digits 0 to 9 in some order, but it also has a rather 
 * interesting sub-string divisibility property.
 *
 * Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, 
 * we note the following:
 *   d2d3d4=406 is divisible by 2
 *   d3d4d5=063 is divisible by 3
 *   d4d5d6=635 is divisible by 5
 *   d5d6d7=357 is divisible by 7
 *   d6d7d8=572 is divisible by 11
 *   d7d8d9=728 is divisible by 13
 *   d8d9d10=289 is divisible by 17
 *
 * Find the sum of all 0 to 9 pandigital numbers with this property.
 */

#include <iostream>
#include <algorithm>
#include <bitset>
#include "euler/digits.hpp"
#include "euler.h"

BEGIN_PROBLEM(43, solve_problem_43)
	PROBLEM_TITLE("Pandigital numbers with sub-string divisibility property")
	PROBLEM_ANSWER("16695334890")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("n!")
	PROBLEM_SPACE_COMPLEXITY("n")
END_PROBLEM()

// multi - list of multipliers
// k - try divisors[k]
// tail - last two digits required
// number - current partial number
// mask - current digit mask
static long long search(const int multi[], int k, int tail, int number[10], std::bitset<10> &mask)
{
	long long sum = 0;
	for (int n = multi[k]; n < 1000; n += multi[k])
	{
		if (n % 100 == tail && !mask.test(n / 100))
		{
			number[k + 1] = n / 100;
			mask.set(n / 100);
			if (k > 0)
			{
				sum += search(multi, k - 1, n / 10, number, mask);
			}
			else if (mask.test(0))
			{
				for (int d = 1; d <= 9; d++)
				{
					if (!mask.test(d))
					{
						number[0] = d;
						long long x = euler::from_digits<10, long long>(&number[0], &number[10]);
						sum += x;
						// std::cout << "Found " << x << std::endl;
					}
				}
			}
			mask.reset(n / 100);
		}
	}
	return sum;
}

static void solve_problem_43()
{
	const int multi[] = { 2, 3, 5, 7, 11, 13, 17 };

	long long sum = 0;
	std::bitset<10> mask;
	int k = 6;
	for (int n = multi[k]; n < 1000; n += multi[k])
	{
		int d1 = n % 10;
		int d2 = (n / 10) % 10;
		int d3 = (n / 100) % 10;
		if (d1 == d2 || d2 == d3 || d1 == d3)
			continue;

		std::bitset<10> mask;
		mask.set(d1);
		mask.set(d2);
		mask.set(d3);
		int number[10] = {-1};
		number[9] = d1;
		number[8] = d2;
		number[7] = d3;
		long long x = search(multi, 5, n / 10, number, mask);
		sum += x;
	}
	std::cout << sum << std::endl;
}
